import sys

### Classes added for assignment 3 to build and play with the heap###

''' EXAMPLE USE
cons (1, cons(2, cons(3,[])))

a = ConCar(false, 3)
b = ConCdr(false, None)
c = ConCell(a,b)
d = head.add(c)

e = ConCar(false, 2)
f = ConCdr(false, d)
g = ConCell(e,f)
h = head.add(g)

i = ConCar(false, 1)
j = ConCdr(false, h)
k = ConCell(i,j)
l = head.add(k)

return k or l ??
'''
# Class representing a ConCell which is a single cell of the heap array
class ConCell :
	conCar = ""
	conCdr = ""
	pos = 0
	head = False
	
	def __init__ (self, index, car, cdr, head = False):
		self.pos = index
		self.conCar = car
		self.conCdr = cdr
		self.head = False
	
	def reset(self):
		if isinstance(self.conCar, ConCar):
			self.conCar.reset()
		if isinstance(self.conCdr, ConCdr):
			self.conCdr.reset()

	def __str__(self):
		if self.head == True :
			return "[ " + str(self.conCar) + str(self.conCdr) + "]"
		else :
			return str(self.conCar) + str(self.conCdr)

	def debugInfo(self):
		return "[" + str(self.pos) + ", " +\
			self.conCar.debugInfo() + \
			self.conCdr.debugInfo() + "]"

# Class for the car variable of a ConCell	
class ConCar :
	value = None
	listMark = False
	
	def __init__ (self, val = None, lmark = False):
		self.value = val
		self.listMark = lmark

	def next(self, lheap):
		if isinstance(lheap, Heap) == False:
			print "input is not a Heap"
			return None
		if self.listMark == True:
			return lheap[self.value] 
		else:
			return None
	
	def reset(self):
		self.value = None
		self.listMark = False
	
	def __str__(self):
		if self.listMark == False:
			ret = str(self.value)
		else:
			'Make sure were not pointing to ourself'
			if Heap.lHeap[self.value].conCar == self :
				ret = " "
			else :
				ret = str(Heap.lHeap[self.value])
		return ret

	def debugInfo(self):
		return "(" + str(self.value) + \
				", ls=" + str(self.listMark) + \
				")"
		
# Class for the cdr variable of a ConCell
class ConCdr(ConCar) :
	gcMark = False
	
	def __init__ (self, val = -1, lmark = True, gcmark = False):
		self.value = val
		self.gcMark = gcmark
		self.listMark = lmark
	
	def reset(self):
		self.value = -1
		self.listMark = True
		gcMark = False
	
	def __str__(self):
		if self.value == -1:
			ret = " "
		else:
			if Heap.lHeap[self.value].conCdr == self :
				ret = " "
			else :
				ret = ", " + str(Heap.lHeap[self.value])
		return ret
			
	def debugInfo(self):
		return "(" + str(self.value) + \
				", ls=" + str(self.listMark) + \
				", gc=" + str(self.gcMark) + \
				")"

class Observer:
    def setup(self, object):
        pass

class MarkGCObserver(Observer):
    def setup(self, object):
        if isinstance(object, ConCell):
            object.conCdr.gcMark = True 

class PrintObserver(Observer):
    sList = [] 
    def setup(self, object):
        if isinstance(object, ConCell):
            self.sList.append(str(object))

# Class for the heap
class Heap:
	def __init__(self, size):
		self.iMaxSize = size
		for i in range(size):
			car = ConCar()
			cdr = ConCdr()
			con = ConCell(i,car,cdr)
			self.lHeap.append(con)
		self.lAvail[0] = (0, size)

	def __getitem__(self, index):
		if index >= 0 and index < self.iMaxSize: 
			return self.lHeap[index]
		else:
			return None
		
	def getConCell(self):
		'''
		return the next available ConCell
		otherwise return None
		'''
		ret = None 
		pos = self.__getNextAvailPos()
		if pos >= 0:
			ret = self.lHeap[pos]
		else:
			self.garbageCollect()
			# try again
			pos = self.__getNextAvailPos()
			if pos >= 0:
				ret = self.lHeap[pos]
			else:
				print "Heap Error !- out of heap memory and unable to release any more"
				sys.exit(1)
		return ret

	def __getNextAvailPos(self):
		'''
		find the postion integer of the next available ConCell of the heap
		'''
		(pos, size) = self.lAvail[0]
		if size == 0:
			#print "__getNextAvailPos size = 0"
			return -1
		ret = pos
		size = size - 1
		if size == 0:
			if len(self.lAvail) > 1:
				#print "pop out avail block"
				self.lAvail.pop(0)
			else:
				self.lAvail[0] = (-1, size)
		else:
			pos += 1
			self.lAvail[0] = (pos, size)
		return ret
		
	def setNameTable(self, nt):
		self.dNameTable = nt

	def garbageCollect(self):
		print "Heap Info - collect garbage"
		self.mark()
		self.sweep()
		pass

	def mark(self):
		'''
		mark gcMark for all used con cells 
		'''
		#print "mark"
		if len(self.dNameTable) > 0:
			obs = MarkGCObserver()
			for key in self.dNameTable.keys():
				value = self.dNameTable[key]
				if isinstance(value, ConCell):
					DFS(value, self, obs)

	def sweep(self):
		'''
		reset all unused con cells
		and claim available memory space for lAvail
		'''
		#print "sweep"
		pos = -1 
		size = 0
		self.lAvail = []
		for i in range(self.iMaxSize):
			cell = self.lHeap[i]
			if cell.conCdr.gcMark == False:
				cell.reset()
				# count available heap block
				if pos == -1:
					pos = i
				if pos >= 0:
					size += 1
			else:
				cell.conCdr.gcMark = False
				if pos >= 0:
					self.lAvail.append((pos,size))
					pos = -1
					size = 0
		if pos >= 0:
			self.lAvail.append((pos,size))

		if len(self.lAvail) == 0:
			self.lAvail.append((-1,0))
	
	def __str__(self):
		ret = "============heap===============\n"
		for i in range(self.iMaxSize):
			ret += self.lHeap[i].debugInfo()+"\n"
		ret += "===============================\n"
		return ret

	lHeap = []
	iMaxSize = 0
	lAvail = [(0,0)]
	dNameTable = {}

# function for adding lists to memory
def new(L,heap):
	cdr_indx =-1
	for e in reversed(L):
                
		consCell = heap.getConCell()
		if consCell != None:

			if type(e)==type(list()):
				#print 'type: List'
				conList = new(e,heap)
				#consCell = heap.getConCell()
				consCell.conCar.value = conList.pos
				consCell.conCar.listMark = True
				consCell.conCdr.value = cdr_indx
				consCell.conCdr.listMark = True

			elif type(e)==type(ConCell(None,None,None)):
				#print 'type: ConCell'
				consCell.conCar.value = e.pos
				consCell.conCar.listMark = True
				consCell.conCdr.value = cdr_indx	
				consCell.conCdr.listMark = True
						
			else:
				#consCell = heap.getConCell()
				#print "else"
				consCell.conCar.value = e
				consCell.conCdr.value = cdr_indx
				consCell.conCdr.listMark = True
			cdr_indx = consCell.pos
			#print consCell
		else:
			#throw error?
			#or return a value that indicates memory not allocated
			#may be break from the loop as well
			consCells = None
                
	consCell.head = True
	return consCell

# function to traverse the linked list
def DFS(root, heap, observer):
	#print "DFS"
	if isinstance(root, ConCell) == False:
		print "root is not a ConCell"
		return
	if isinstance(heap, Heap) == False:
		print "heap is not a Heap"
		return
	if isinstance(observer, Observer) == False:
		print "observer is not an Observer"
		return

	observer.setup(root)
	left = root.conCar.next(heap) 
	if left != None: 
		DFS(left, heap, observer)
	right = root.conCdr.next(heap)
	if right != None:
		DFS(right, heap, observer)
	
		
iHeapSize = 10
heap = Heap(iHeapSize)


